// Problem 037: Truncatable primes
// The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.
// Find the sum of the only eleven primes that are both truncatable from left to right and right to left.
// NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

package main

import (
	"fmt"
	"projecteuler/euler"
)

func p037() {
	ans := 23 + 53
	if len(candidates) > 0 {
		candidates = make(map[int]int)
	}
	for l := 10; l <= 100000; l *= 10 {
		getCandidate037(l, 0)
	}
	for k := range candidates {
		if !check037(k) {
			delete(candidates, k)
		} else {
			ans += k
		}
	}
	fmt.Println("Problem 037:", ans)
}

func getCandidate037(gt, n int) {
	if n > gt {
		if euler.IsPrime(n) {
			candidates[n] = 0
		}
		return
	}
	P := [4]int{1, 3, 7, 9}
	for i := 0; i < 4; i++ {
		getCandidate(gt, n*10+P[i])
	}
}

func check037(p int) bool {
	n := p
	nlen := 1
	for n > 10 {
		n /= 10
		if !euler.IsPrime(n) {
			return false
		}
		nlen++
	}
	n = p
	for n > 10 {
		n %= euler.TenPower[nlen]
		if !euler.IsPrime(n) {
			return false
		}
		nlen--
	}
	return true
}
